package my.jwds.p821;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class ShortestToChar {

    public static void main(String[] args) {

        Solution1 obj = new Solution1();
        long start = System.currentTimeMillis();
        System.out.println(obj.shortestToChar( "loveleetcode", 'e'));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    static class Solution {


        public int[] shortestToChar(String s, char c) {
            int len = s.length(),res[] = new int[len],lastE = -100000;
            Arrays.fill(res,Integer.MAX_VALUE);
            char[]chars = s.toCharArray();
            for (int i = 0; i < len; i++) {
                if (chars[i] == c)lastE = i;
                res[i] = Integer.min(Math.abs(i-lastE),res[i]);
            }
            lastE = Integer.MAX_VALUE;
            for (int i = len-1; i >= 0; i--) {
                if (chars[i] == c)lastE = i;
                res[i] = Integer.min(lastE-i,res[i]);
            }
            return res;
        }

    }

    static class Solution1 {
        public int[] shortestToChar(String s, char c) {
            int n = s.length();
            int[] ans = new int[n];
            Arrays.fill(ans, -1);
            Deque<Integer> d = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                if (s.charAt(i) == c) {
                    d.addLast(i);
                    ans[i] = 0;
                }
            }
            int[] dirs = new int[]{-1, 1};
            while (!d.isEmpty()) {
                int t = d.pollFirst();
                for (int di : dirs) {
                    int ne = t + di;
                    if (ne >= 0 && ne < n && ans[ne] == -1) {
                        ans[ne] = ans[t] + 1;
                        d.addLast(ne);
                    }
                }
            }
            return ans;
        }
    }


}